/**
 类似于背包问题
 * @param {number[]} nums
 * @return {boolean}
 */
export var canPartition = function (nums) {
  const sm = nums.reduce((p, c) => p + c, 0)

  //  1，如果sum(nums)不是偶数，肯定不能分成两分相等的，return false
  if (sm % 2 !== 0) return false
  // 背包问题：背包最大容量为 sm / 2
  const target = sm / 2

  const dp = new Array(nums.length).fill(0).map(() => new Array(target + 1).fill(false))

  for (let i = 0; i < nums.length; i++) {
    const num = nums[i]
    for (let j = 1; j <= target; j++) {
      if (i === 0) {
        if (num === j) dp[i][j] = true
      } else if (dp[i - 1][j] || num === j) dp[i][j] = true
      else if (num < j) dp[i][j] = dp[i - 1][j - num]
    }
  }
  return dp[nums.length - 1][target]
}
